package com.data.simulation;

import com.data.tree.TreeNode;

import java.util.LinkedList;

/**
 * @author zsj
 * @date 2023/9/27 15:47
 * <p>
 * 非递归实现 前中后 遍历二叉树
 */
public class TreeWithNoRecursion {
    public static void main(String[] args) {
        /*
        1
     2    3
   4    5    6
         */
        TreeNode node = new TreeNode(1,
                new TreeNode(2, new TreeNode(4), null),
                new TreeNode(3, new TreeNode(5), new TreeNode(6)));

        TreeNode cur = node;

        /*
        使用栈来记录回去的路
        并且每次回去都会把父节点的右边节点作为当前节点
         */
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
//                System.out.println("去" + cur.value);
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.println("回" + pop.value);
                cur = pop.right;
            }
        }

    }


}
